from mode import *


class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def byteSum(a, b):
            res = 0
            while a != 0:
                res += a % 10
                a = a // 10
            while b != 0:
                res += b % 10
                b = b // 10

            return res

        dp = [[0 for _ in range(n)] for _ in range(m)]

        def dfs(i, j):
            if i >= m or j >= n or byteSum(i, j) > k or dp[i][j] == 1:
                return 0
            dp[i][j] = 1

            return 1 + dfs(i + 1, j) + dfs(i, j + 1)

        return dfs(0, 0)


if __name__ == "__main__":
    A = Solution()
    print(A.movingCount(3, 2, 17))
